/**392. 判断子序列
 * - 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 * - 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
 */
export function isSubsequence(s: string = "abc", t: string = "ahbgdc"): boolean {
    const sLen = s.length
    const tLen = t.length
    /**dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。 */
    const dp = Array.from({ length: sLen + 1 }, () => new Array<number>(tLen + 1).fill(0))
    for (let i = 1; i <= sLen; i++) { //因为dp数组含义是相对于i-1的，所以要注意这里的起始条件
        for (let j = 1; j <= tLen; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1; //如果相等，那么+1，代表相同子序列长度+1
            } else {
                dp[i][j] = dp[i][j - 1] //如果不相等，那么就让j进行回退 （i不用，因为s是要对比的子序列，不能删除）
            }
        }
    }
    if (dp[sLen][tLen] === sLen) return true //如果最终得到的子串长度和s长度相同，说明成功
    return false
}
/**115. 不同的子序列
 *  - 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
 *  - 输入：s = "rabbbit", t = "rabbit"
 *  - 输出：3
 *  - 解释：
 *  - 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
 *  - 原：rabbbit
 *  - 得：rabb it
 *  - 得：rab bit
 *  - 得：ra bbit
 */
export function numDistinct(s: string = "rabbbit", t: string = "rabbit"): number {
    //没看懂！！

    //https://programmercarl.com/0115.不同的子序列.html#思路
    const sLen = s.length
    const tLen = t.length
    /**以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
     * - 当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; （分为 用s[i - 1]来匹配和不用）
     * - 当不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]
     */
    const dp = Array.from({ length: sLen + 1 }, () => new Array<number>(tLen + 1).fill(0))
    for (let i = 0; i < dp.length; i++)dp[i][0] = 1 //初始化
    for (let i = 1; i <= sLen; i++) {
        for (let j = 1; j <= sLen; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            } else {
                dp[i][j] = dp[i - 1][j]
            }
        }
    }
    return dp[sLen][tLen]
}
/**583. 两个字符串的删除操作
 * -给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
 * - 每步可以删除任意一个字符串中的一个字符
 */
export function minDistance(word1: string = "sea", word2: string = "eat"): number {
    //https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html#%E6%80%9D%E8%B7%AF
    const len1 = word1.length
    const len2 = word2.length
    /** dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
     * - 当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];
     * - 否则，
     * - 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
     * - 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
     * - 情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2
     * - dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
     */
    const dp = Array.from({ length: len1 + 1 }, () => new Array<number>(len2 + 1).fill(0))
    for (let i = 0; i <= len1; i++) dp[i][0] = i;
    for (let j = 0; j <= len2; j++) dp[0][j] = j;

    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
            }
        }
    }
    return dp[len1][len2]
}
/**72. 编辑距离
 * - 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 
 */
export function editDistance(word1: string = "horse", word2: string = "ros"): number {
    const len1 = word1.length
    const len2 = word2.length
    /** 
     * - dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]  （）
     * - 
     * - if (word1[i-1] == word2[j-1]) 相同字母尽量保留 就不操作，即 dp[i][j] = dp[i-1][j-1]  （继承上一个的数据）
     * 
     * - else 否则就需要进行操作，有下面的三种操作： 
     *  1. 删 dp[i][j] = dp[i-1][j] + 1  （i-1是因为删了一个，所以下标往前推、+1是因为删除是一个操作）
     *  2. 增 dp[i][j] = dp[i][j-1] + 1  （在word1增加，相当于在word2上减少，所以在j上操作）
     *  3. 改 dp[i][j] = dp[i-1][j-1] + 1 (就是在上一个的基础上+1即可)
     * 
     * - 初始化：观察上面的分析，可以知道所有数据都是基于 dp[0][j]和dp[i][0]，所以要初始化这两行
     * - dp[i][0]表示长度i的word1和长度0的字符串需要的转换次数，那么直接就是 i - 0 = i 即可，同理j一样
     * 
     */
    const dp = Array.from({ length: len1 + 1 }, () => new Array<number>(len2 + 1).fill(0))
    //初始化：表示长度i的word1和长度0的字符串需要的转换次数，要不就是一直增，要不就是一直减，所以直接初始化为 i 和 j 就行
    for (let i = 0; i <= len1; i++) dp[i][0] = i;
    for (let j = 0; j <= len2; j++) dp[0][j] = j;

    for (let i = 1; i <= len1; i++) {
        for (let j = 1; j <= len2; j++) {
            //因为相同的字母，操作数为0是最优解，所以优先保留这个字母
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]
            } else { //字母不相同的时候，可以增删改，选一个最优解 
                dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1//取三个操作的最小值。因为+1都是一样的，所以可以提取出来
            }
            // console.table(dp); 
        }
    }

    return dp[len1][len2]
}